#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <mpi.h>

void GeraPalavra(char palavraRecebida[], char caracteresEntrada[], int posicaoCaracterEntrada);
void PreencheVetor(char *vetor);
void PreparaArquivo();
int  Compara(const void *a, const void *b);

int main(int argc, char *argv[]) {
	PreparaArquivo();
	FILE *arquivo;
	long numeroPalavras, numeroPalavrasProcesso, numeroPalavras2;
	int i = 0;

	arquivo = fopen ( "final.txt" , "r" );

	if (arquivo == NULL) { 
		exit (1);
	}
    
    fscanf(arquivo, "%ld", &numeroPalavras); //pega o número total de palavras escrito no arquivo
    
    numeroPalavras2 = numeroPalavras; //armazena em um auxiliar

	//MPI
	int ret, numeroProcessos, rank; 
    MPI_Status status;
	
    if(MPI_Init(&argc, &argv) != MPI_SUCCESS)
		exit(1);
		
    MPI_Comm_size(MPI_COMM_WORLD, &numeroProcessos);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    numeroPalavrasProcesso = ( numeroPalavras / (numeroProcessos - 1) ) + 1; //número de palavras que cada processo recebera
    
    char listaPalavrasEntrada[numeroPalavrasProcesso][100], listaPalavrasSaida[numeroPalavrasProcesso][100]; //listas de palavras que os processos receberao
    char caracteresEntrada[50], caracteresSaida[50]; //lista de caracteres que possuem os caracteres suficientes para gerar as palavras
    double inicioFilho = 0, fimFilho = 0, inicio = 0, fim = 0; //variaveis de tempo
        
    if(rank == 0) {
    	long numeroPalavrasGeradas = 0, numeroPalavrasGeradasEntrada = 0; //numero de palavras geradas
    	int j;
    	float porcentagem; //porcentagem de palavras geradas
    	
		inicio = MPI_Wtime(); //inicia a execução.
			
		PreencheVetor(caracteresSaida);
			
		for(i = 1; i < numeroProcessos; i++) {
			if(numeroPalavrasProcesso < numeroPalavras2) {
				for(j = 0; j < numeroPalavrasProcesso; j++) { //lendo as palavras do arquivo e armazenando na lista
					fscanf(arquivo, "%s", listaPalavrasSaida[j]);
				}
				numeroPalavras2 = numeroPalavras2 - numeroPalavrasProcesso; 
			}
			else { //ultimo processo recebe um numero menor de palavras
				for(j = 0; j < numeroPalavras2; j++) {
					fscanf(arquivo, "%s", listaPalavrasSaida[j]); //lendo as palavras do arquivo e armazenando na lista
				}
				listaPalavrasSaida[j][0] = -1; //como nao preencheu a lista inteira por ser ultimo processo seta o final com -1 
			}

			MPI_Send(&listaPalavrasSaida, (numeroPalavrasProcesso)*(100), MPI_CHAR, i, 1, MPI_COMM_WORLD); //envia lista de palavras
			MPI_Send(&caracteresSaida, 50, MPI_CHAR, i, 1, MPI_COMM_WORLD); //envia lista de caracteres
			MPI_Send(&inicio, 1, MPI_DOUBLE, i, 1, MPI_COMM_WORLD); //envia tempo inicial
		}
		
		for(i = 1; i < numeroProcessos; i++) {
			MPI_Recv(&numeroPalavrasGeradasEntrada, 1, MPI_LONG, i, 1, MPI_COMM_WORLD, &status); //recebe o numero de palavras geradas de cada filho
			MPI_Recv(&fim, 1, MPI_DOUBLE, i, 1, MPI_COMM_WORLD, &status); //recebe o tempo final calculado
			numeroPalavrasGeradas += numeroPalavrasGeradasEntrada; //soma o numero de palavras geradas de cada filho
		}
		
		printf("%ld palavras geradas\n", numeroPalavrasGeradas);
		
	    //tempo de execução
    	double  tempo = (fim - inicio)/60;
    	
    	porcentagem = ((float)numeroPalavrasGeradas/(float)numeroPalavras)*100;
    	
    	printf(" %.2f porcento do total de palavras (%ld) foram geradas em %.2lf minutos\n", porcentagem, numeroPalavras, tempo);
    }
    else {
    	int j, posicaoCaracterEntrada = 26/*"ponteiro" para o vetor caracteresEntrada, na posição 26 pois tem 26 letras no vetor*/;
    	long numeroPalavrasGeradasSaida = 0; /*contador para o numero de palavras geradas*/

    	MPI_Recv(&listaPalavrasEntrada, (numeroPalavrasProcesso)*(100), MPI_CHAR, 0, 1, MPI_COMM_WORLD, &status);//recebe o pedaço do arquivo para gerar as palavras
    	MPI_Recv(&caracteresEntrada, 50, MPI_CHAR, 0, 1, MPI_COMM_WORLD, &status); //recebe o vetor dos caracteres criado no pai
    	MPI_Recv(&inicioFilho, 1, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD, &status); //recebe tempo inicial
    	
    	for(i = 0; i < numeroPalavrasProcesso; i++) { //laço para percorrer o pedaço do arquivo recebido do pai
    		if(listaPalavrasEntrada[i][0] == -1) { //chegou no final da lista recebida pelo pai provavelmente no ultimo filho
    			i = numeroPalavrasProcesso;
    		} 
    		else {
				for(j = 0; j < strlen(listaPalavrasEntrada[i]); j++) {
					if(!isalpha(listaPalavrasEntrada[i][j])) { //se o char não for alfabético armazena ele no vetores de caracteres para gerar a palavraRecebida
						caracteresEntrada[posicaoCaracterEntrada] = listaPalavrasEntrada[i][j];
						posicaoCaracterEntrada++;
						caracteresEntrada[posicaoCaracterEntrada] = -1; //seta o final do vetor de caracteres com -1
					}
				}
	   					
	   			printf("Filho %d gerando  %s...\n", rank, listaPalavrasEntrada[i]);
				GeraPalavra(listaPalavrasEntrada[i], caracteresEntrada, posicaoCaracterEntrada);//gerar palavraRecebida
				printf("Filho %d gerou %s!\n", rank, listaPalavrasEntrada[i]);
	   					
				numeroPalavrasGeradasSaida++; //incrementa o numero de palavras geradas    	
				
				fimFilho = MPI_Wtime();
				if((fimFilho - inicioFilho)/60 > 3) { //condicao de parada
					i = numeroPalavrasProcesso;
				}			
	   					
	   			posicaoCaracterEntrada = 26; //reinicia o "ponteiro" para o vetor de caracteres
	   			caracteresEntrada[posicaoCaracterEntrada] = -1; //reinicia o vetor de caracteres
    		}
    	}
    	
    	MPI_Send(&numeroPalavrasGeradasSaida, 1, MPI_LONG, 0, 1, MPI_COMM_WORLD); //envia o numero de palavras geradas
    	MPI_Send(&fimFilho, 1, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD); //envia o tempo final
    }	

	MPI_Finalize();
	fclose (arquivo);
	
    return 0;	  
}

void GeraPalavra(char palavraRecebida[], char caracteresEntrada[], int posicaoCaracterEntrada) {
	char palavraAleatoria[100]/*palavraRecebida que será gerada randomicamente*/, 
		 auxPalavra[6]/*Auxiliar para pegar parte de palavras maiores que 5*/;
	int tamanhoPalavra, i, j = 0, k;
	
	srand(time(NULL));
	
	tamanhoPalavra = strlen(palavraRecebida); //pega o tamanho da palavraRecebida
	
	if(tamanhoPalavra > 5) {
		for(i = 0; i <= tamanhoPalavra; i++) { //percorrendo a palavraRecebida dividindo-a em pedaços de 5
			if(j == 5 || i == tamanhoPalavra) { //chegou ao fim da palavraRecebida
				auxPalavra[j] = '\0';
				j = 0;
				
				do { //gera palavras menores que 5
					for(k = 0; k < strlen(auxPalavra); k++) { 
						palavraAleatoria[k] = caracteresEntrada[rand() % posicaoCaracterEntrada]; //gera a palavraRecebida randomicamente com os caracteres que estão no vetor de caracteres que aquela palavraRecebida possui
					}
					palavraAleatoria[k] = '\0';
				} while(strcmp(auxPalavra, palavraAleatoria) != 0);
				
				if(i != tamanhoPalavra) { //esse if server para não pular letra ao cortar a palavraRecebida
					auxPalavra[j] = palavraRecebida[i];
					j++;
				}
			}
			else { //pegando caracter por caracter
				auxPalavra[j] = palavraRecebida[i];
				j++;	
			}
		}
	}
	else {
		do { //gera palavras menores que 5
			for(i = 0; i < tamanhoPalavra; i++) { 
				palavraAleatoria[i] = caracteresEntrada[rand() % posicaoCaracterEntrada]; //gera a palavraRecebida randomicamente com os caracteres que estão no vetor de caracteres que aquela palavraRecebida possui
			}
			palavraAleatoria[i] = '\0';
		} while(strcmp(palavraRecebida, palavraAleatoria) != 0);
	}
}

void PreencheVetor(char *vetor){
	int i;
	for(i = 97; i < 123; i++) { //preenchendo o vetor de caracteres com as letras do alfabeto, minusculas
    		vetor[i-97] = i;
    	}
    	vetor[i-97] = -1;
}

void PreparaArquivo(){
	FILE *arquivoInicial, *arquivoFinal;
	char caracter, palavra[100], **listaPalavras;
	int posicaoPalavra = 0, i, posicaoMatriz = 0, numeroPalavras = 0;
	clock_t inicio = 0, fim = 0;
    inicio = clock();

	listaPalavras = (char**)malloc( 200000 * sizeof(char*) );
  	for(i = 0; i < 200000; i++) {
    	listaPalavras[i] = (char*)malloc( 100 * sizeof(char) );
  	}

	arquivoInicial = fopen ( "palavras2.txt" , "r" );

	if (arquivoInicial == NULL) {
		fputs ("File error\n",stderr);
		exit (1);
	}

	printf("Convertendo o arquivo...\n");
	while(!feof(arquivoInicial)) {
		fscanf (arquivoInicial,"%c",&caracter);
		if(caracter != ',' && caracter != ' ' && caracter != '\n' && caracter != '\r') {
			palavra[posicaoPalavra] = tolower(caracter);
			posicaoPalavra++;
		}
		else {
			palavra[posicaoPalavra] = '\0';
			posicaoPalavra = 0;
			numeroPalavras++;

            //Imprime . ao chegar as 100000 palavras
			if(numeroPalavras%100000 == 0 && numeroPalavras != 0) {
                printf(". ");
            }	
			for(i = 0; i < 200000; i++) {
                if(i == posicaoMatriz) { //chegou no fim da lista e nao tem a palavra
                    strcpy(listaPalavras[i], palavra);
                    posicaoMatriz++;
                    i = 200000;
                }
                else if(strcmp(palavra, listaPalavras[i]) == 0) {
                    i = 200000;
                }
            }
		}
	}

	fclose (arquivoInicial);

	qsort(listaPalavras, posicaoMatriz, sizeof(char*), Compara);

	arquivoFinal = fopen ( "final.txt" , "w" );

	if (arquivoFinal == NULL) {
		fputs ("File error\n",stderr);
		exit (1);
	}

	fprintf(arquivoFinal, "%d\n", posicaoMatriz);

	for(i = 0; i < posicaoMatriz; i++) {
		fprintf(arquivoFinal, "%s\n", listaPalavras[i]);
	}
	fclose (arquivoFinal);
}

int Compara(const void *a, const void *b) {
    return strcmp(*(char **)a, *(char **)b);
}
